Modern computer graphics extensively uses matrices and matrix methods to represent graphical objects and operations. For example, in the context of 2D graphics, a point P may be represented as a column vector P=[x y].sup.t, and multiplied by the rotation matrix ##EQU1##
in order to achieve a counterclockwise rotation by angle .theta.. In other words, the point ##EQU2##
is the rotated image of point P. It is noted that the superscript t associated with a matrix or vector argument indicates transposition.
Similarly, in the context of 3D graphics, a point P may be represented as a column vector P=[x y ].sup.t, and multiplied by a 3.times.3 rotation matrix R in order to achieve a 3D rotation; i.e. the resultant point P'=R.multidot.P is the rotated image of point P. For example, the matrix ##EQU3##
achieves a rotation of angle .theta. about the z axis when multiplied by point P. Rotations about the x and y axes respectively are achieved by the matrices ##EQU4##
respectively.
It is a basic geometric fact that any 3D rotation can be achieved by applying in succession a rotation about the x axis, a rotation about the y axis, and a rotation about the z axis. [Similar statements can be made about any ordering of the axial rotations.] Thus, the rotation matrices may be defined as the set of all matrices generated by the products R.sub.x (.o slashed.).multidot.R.sub.y (.phi.).multidot.R.sub.z (.theta.) where the angles .o slashed., .phi., and .theta. vary freely. However, one may equivalently (and more usefully) characterize the rotation matrices as the set of matrices A which (a) are orthogonal and (b) have determinant equal to one. To say that a matrix A is orthogonal means that (i) all its rows have length one, and (ii) each row is perpendicular to the other rows. In mathematical notation, the orthogonality conditions (i) and (ii) may be summarized by the matrix equation AAt=I, where the matrix I is the identity matrix. Using the later characterization of rotation matrices as orthogonal matrices having determinant one, it is an elementary exercise to show that the product of two rotation matrices is itself a rotation matrix. In fact, a product of arbitrarily many rotation matrices is also a rotation matrix.
In graphical computing systems, it is quite typical to represent a graphical object as a collection of vertices {P.sub.i }. In order to rotate the graphical object, each vertex P.sub.i of the collection is multiplied by a rotation matrix R which represents the desired rotation. The resultant vertices P'.sub.i =RP.sub.i from the matrix multiplication may be used to render the rotated graphical object on a display screen.
FIG. 1 illustrates two successive rotations of a cube centered about the origin of a coordinate system {x,y,z}. In an initial orientation U.sub.0, the cube is aligned with edges parallel to the coordinate axes. A first rotation of the cube may be achieved by multiplying the vertices {P.sub.i } of the cube in the initial orientation U.sub.0 by a first rotation matrix R.sub.1. For example, vertex P.sub.1 of the cube in orientation U.sub.0 may be represented as a column vector P.sub.1 =[x.sub.1 y.sub.1 z.sub.1 ].sup.t, where x.sub.1, y.sub.1, and z.sub.1 are the coordinates of vertex P.sub.1 with respect to the coordinate system {x,y,z}. The rotated image of vertex P.sub.1, depicted as vertex P'.sub.1 in orientation U.sub.1, is determined by the matrix-vector product P'.sub.1 =R.sub.1.multidot.P.sub.1. Similarly, each vertex P.sub.i of the cube in orientation U.sub.0 is multiplied by the rotation matrix R.sub.1 to determine a corresponding vertex P'.sub.i in orientation U.sub.1. The vertices {P'.sub.i } may be used to render the cube in orientation U.sub.1 on a display screen.
A second rotation may be achieved by multiplying the vertices {P'.sub.i } of the cube in orientation U.sub.1 by a second rotation matrix R.sub.2. Thus, the vertices {P".sub.i } of the cube in orientation U.sub.2, i.e., after the second rotation, are given by P".sub.i =R.sub.2.multidot.P'.sub.i. It is noted that the combined effect of the two rotations may be achieved with a single rotation matrix R equal to the matrix product R.sub.2 R.sub.1 ; i.e., multiplying the vertices {P.sub.i } of the cube in orientation U.sub.0 by the rotation matrix R=R.sub.2 R.sub.1 generates the corresponding vertices {P.sub.i } in orientation U.sub.2. Thus, the rotation matrix R may be interpreted as a representation of orientation U.sub.2. In fact, each orientation U.sub.i may be represented by the matrix required to generate the vertices of that orientation from the initial orientation U.sub.0. Thus, initial orientation U.sub.0 is represented by the identity matrix I, and orientation U.sub.1 is represented by the rotation matrix R.sub.1.
Quite often in computer graphics, it is desirable to apply a series of rotations in succession to a graphical object. As described above, the graphical object is typically represented in an initial orientation as a collection of vertices {P.sub.i }. Given a series of rotation matrices R.sub.1,R.sub.2, . . . , R.sub.n which represent the desired rotations, there are two fundamental methods for computing the vertices of the graphical object after each successive rotation. Let {P.sub.i.sup.(k) } denote the vertices of the graphical object after the first k rotations have been applied where k varies from 1 to n. In a first method, the vertices of a current orientation are computed in terms of the vertices of the previous orientation. Namely, EQU P.sub.i.sup.(k) =R.sub.k.multidot.P.sub.i.sup.(k-1)
where P.sub.i.sup.(0) =P.sub.i. After the vertices {P.sub.i.sup.(k) } are computed, they are typically used to render the updated orientation of the graphical object on a display screen.
In a second method, the succession of rotations may be generated by iteratively computing a sequence of matrices U.sub.k according to the relation U.sub.k =R.sub.k U.sub.k-1 with U.sub.0 =I. After matrix U.sub.k is computed, the vertices {P.sub.i.sup.(k) } of the graphical object in the k.sup.th orientation may be computed directly from the vertices {P.sub.i } of the initial orientation using the relation EQU P.sub.i.sup.(k) =U.sub.k.multidot.P.sub.i.
Thus, the matrix U.sub.k represents the orientation of the graphical object after the first k rotations have been applied. This second method for generating a series of rotations is generally preferred over the first method for reasons which will become fully apparent below.
By repeatedly applying the recursive relation U.sub.k =R.sub.k U.sub.k-1 for successively decreasing values of the index k, it follows that EQU U.sub.k =R.sub.k R.sub.k-1 . . . R.sub.2 R.sub.1.
Since the arbitrary product of rotation matrices is itself a rotation matrix, each of the orientation matrices U.sub.k is a rotation matrix, provided the matrix multiplications generating U.sub.k are preformed on an ideal machine with infinite precision.
In actuality, however, one can only approximate the ideal situation. In general, the coefficients of a rotation matrix R cannot be represented exactly with finite precision memory. Thus, any memory representation R of a rotation matrix R must necessarily be approximate: EQU R=R+.delta.,
where .delta. is an error matrix which includes numeric representation error. In addition to numeric representation error, there are situations where it is desirable to approximate a rotation matrix for the sake of computational efficiency. For example, in order to implement a rotation about one of the axes, say the z axis, through a small angle .DELTA..theta., it is advantageous to approximate the z axis rotation matrix R.sub.z (.DELTA..theta.) using the small angle approximations EQU sin (.DELTA..theta.).apprxeq..DELTA..theta., EQU cos (.DELTA..theta.).apprxeq.1.
Namely, ##EQU5##
A matrix-vector product computed with the approximation matrix R.sub.z (.DELTA..theta.) may be computed with two scalar multiplies, whereas a matrix-vector product computed with the original rotation matrix R.sub.z (.DELTA..theta.) requires four scalar multiplies. Thus, in order to implement a small angle rotation about one of the coordinate axes, it is quite typical to use an approximation to the axial rotation matrix.
Furthermore, consider the situation where a small angle rotation about the x axis is to be followed by a small angle rotation about the y axis. It is possible to implement this pair of rotations by multiplying each vertex P.sub.i of a graphical object by the pair of axial rotations R.sub.x (.DELTA..o slashed.) and R.sub.y (.DELTA..phi.), where .DELTA..o slashed. denotes the angle of rotation about the x axis, and .DELTA..phi. denotes the angle of rotation about the y axis. This computation would require eight scalar multiplies and four scalar additions per vertex P.sub.i. Alternatively, the same pair of rotations may be realized by the approximate rotation matrix ##EQU6##
where .DELTA..phi. denotes the angle of rotation about the x axis, and .DELTA..phi. denotes the angle of rotation about the y axis. Approximation matrix R.sub.xy is derived by computing the product of the axial rotations R.sub.x (.DELTA..o slashed.) and R.sub.y (.DELTA..phi.), and making the small angle replacements for sine and cosine wherever possible. A matrix-vertex product evaluated using the approximate rotation matrix R.sub.xy requires four scalar multiplies and three scalar additions. Thus, a computational advantage may arise from using the approximate rotation matrix R.sub.xy instead of the separate axial rotations R.sub.x (.DELTA..o slashed.) and R.sub.y (.DELTA..phi.) for generating the pair of successive rotations.
The use of computationally efficient approximations to rotation matrices is especially important for generating continuous real-time rotations of a graphical object. In order to create the illusion of continuous motion for a displayed graphical object, a graphical computing system typically displays multiple frames per second, where the graphical object differs by a slight rotation between successive frames. In order to generate the slight rotation between successive frames in real-time, an approximation to a true rotation matrix is quite frequently employed.
Furthermore, it is noted that a graphical computing system quite often includes a position tracking device such as a mouse or track ball. By reading the horizontal displacement .DELTA.u and vertical displacement .DELTA.v of the position tracking device over a small time interval .DELTA.t, it is possible to generate an approximate rotation matrix which corresponds to the instantaneous motion of the position tracking device. For example, a graphical computing system may map the horizontal displacement .DELTA.u and vertical displacement .DELTA.v onto the approximate rotation matrix ##EQU7##
using the relations EQU .DELTA..o slashed.=.alpha..multidot..DELTA.u, EQU .DELTA..phi.=.beta..multidot..DELTA.v,
where .alpha. and .beta. are proportionality constants. The approximate rotation matrix R.sub.xy may then be used to generate a rotation of the graphical object between the current frame and the next frame to be displayed. By repeatedly reading the horizontal and vertical displacements from the position tracking device and applying the corresponding approximate rotation matrices R.sub.xy to update successive frames, a graphical computing system may provide a user manipulating the position tracking device with continuous real-time control of the orientation of a displayed graphical object.
For the reasons elaborated above, in the context of any physical computation of a series of rotations, it is more realistic to consider a series of approximate rotation matrices R.sub.1, R.sub.2, . . . , R.sub.n, where each approximate rotation matrix R.sub.i deviates from the corresponding true rotation matrix R.sub.i by an error matrix .delta..sub.i : EQU R.sub.i =R.sub.i +.delta..sub.i.
Error .delta..sub.i may include numerical representation error, approximation error, and/or measurement error (if the rotation matrix is derived from physical measurements). Furthermore, the matrices U.sub.k which generate the vertices {P.sub.i.sup.(k) } in the second method discussed above are approximated by matrices U.sub.k computed according to the recursive relation U.sub.k =R.sub.k U.sub.k-1 with U.sub.0 =I. If each matrix U.sub.j departs from matrix U.sub.j by error matrix .epsilon..sub.j, i.e., .epsilon..sub.j =U.sub.j -U.sub.j, then EQU U.sub.k =R.sub.k U.sub.k-1 =(R.sub.k +.delta..sub.k)(U.sub.k-1 +.epsilon..sub.k-1) =R.sub.k U.sub.k-1 +R.sub.k.epsilon..sub.k-1 +.epsilon..sub.k U.sub.k-1 +.delta..sub.k.epsilon..sub.k-1 +.delta..sub.c,
where .delta..sub.c is a computation error matrix due to performing the matrix multiplications with finite precision hardware. Since matrix U.sub.k =R.sub.k U.sub.k-1 is a true rotation matrix, approximation matrix U.sub.k departs from a true rotation by error EQU .epsilon..sub.k =U.sub.k -U.sub.k =R.sub.k.epsilon..sub.k-1 +.delta..sub.k U.sub.k-1 +.delta..sub.k.epsilon..sub.k-1 +.delta..sub.c.
The recursive structure of this equation implies that the approximation error .epsilon..sub.k may grow at an exponential rate. Thus, as index k increases, the approximate orientation matrices U.sub.k will eventually diverge significantly from being a true rotation matrix. In practice, this means that the rotated vertices {P.sub.i.sup.(k) } generated from approximation matrix U.sub.k may exhibit unwanted visual artifacts, i.e., visual features which are manifestly inconsistent with a physical rotation. A need therefore exists for a system and method which operates on an approximate rotation matrix M to produce a resultant matrix S(M) which is significantly closer to being a true rotation than the approximate rotation matrix M. In other words, a system and method is desired which compensates for the accumulated error in an approximate rotation matrix. Furthermore, a need exists for an improved multiplication operator on a pair of approximate rotation matrices A and B which could be used to estimate the ordinary matrix product AB, where the resultant L of the improved multiplication operator is closer to being a true rotation than the ordinary matrix product AB.